package 链表;

public class LinkedList<E> {

    static class Node<E>{
       public E val;
        public Node<E> next;
        public Node(E val) {
            this.val = val;
        }
    }
    private int size;
    public Node<E> head;//代表当前链表的头节点
    // 1、无头单向非循环链表实现

    //头插法
    public void addFirst(E data){
        Node<E> node=new Node<>(data);
        node.next=head;
        head=node;
        size++;
        System.out.println();
    }
    //尾插法
    public void addLast(E data){
        Node<E> cur=head;
        Node<E> node=new Node<>(data);
        //如果没有结点，就将新增节点置为头节点
        if(cur==null) {
            head=node;
            return;
        }
        while (cur.next!=null) {
            cur=cur.next;
        }
        cur.next=node;
        size++;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,E data){
        if(index<0||index>size()) {
            throw new indexException("下标异常");
        }
        if(index==0) {
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        Node<E> cur=head;
        while (index!=1) {
            cur=cur.next;
            index--;
        }
        Node<E> curNext=cur.next;
        Node<E> node=new Node<>(data);
        cur.next=node;
        node.next=curNext;
        size++;
    }
    public int size() {
        return size;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(E key){
        Node<E> cur=head;
        while (cur!=null) {
            if(cur.val.equals(key)) {
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    /**
     * 判空
     * @return
     */
    private boolean isEmpty() {
        return head==null;
    }
    //删除第一次出现关键字为key的节点

    public void remove(E key){
        if(isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        if(!contains(key)) {
            System.out.println("不存在该值");
            return;
        }
        Node<E> cur=head;
        //记录key的前一个结点

        Node<E> prev=null;
        while (cur!=null) {
            Node<E> curNext=cur.next;
            if(cur.val.equals(key)) {
                break;
            }
            prev=cur;
            cur=curNext;
        }
        //如果是头删
        if(cur==head) {
            head=head.next;
            return;
        }
        prev.next=prev.next.next;
        size--;
    }
    public void display() {
        Node<E> cur=head;
        while (cur!=null) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //删除所有值为key的节点
    public void removeAllKey(E key){
        Node<E> cur=head;
        Node<E> prev=null;
        while (cur!=null) {
            Node<E> curNext=cur.next;
            if(cur.val.equals(key)) {
                //需要判断头删
                while (cur.val.equals(key)) {
                    cur=cur.next;
                }
                if(prev==null) {
                    head=cur;
                }else {
                    prev.next = cur;
                }
                if (curNext!=null)
                curNext=cur.next;
            }
            prev=cur;
            cur=curNext;
        }
    }
    /**
     * 判断是否是回文链表
     */
    public boolean chkPalindrome(ListNode A) {
        // write code here
        //找到中间结点
        ListNode prev=A;
        ListNode cur=A;

       cur= middleNode(cur);
        //中间结点逆置
        cur=reverseList(cur);
        //从两个头开始进行判断
        while (prev!=null&&cur!=null) {
            if(prev.val!=cur.val) {
                return false;
            }
            prev=prev.next;
            cur=cur.next;
        }
        return true;

    }
    /**
     * 合并两个有序链表
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //不用哨兵位
        ListNode newHead=null;
        ListNode cur=null;
        while (list1!=null&&list2!=null) {
            if(list1.val<list2.val) {
                if(newHead==null) {
                    newHead=list1;
                    cur=newHead;
                }else {
                    cur.next=list1;
                    cur=cur.next;
                }
                list1=list1.next;
            }else {
                if(newHead==null) {
                    newHead=list2;
                    cur=newHead;
                }else {
                    cur.next=list2;
                    cur=cur.next;
                }
                list2=list2.next;
            }
        }
        if(list1!=null) {
            cur.next=list1;
        }
        if(list2!=null) {
            cur.next=list2;
        }
        System.out.println();
        cur.next=null;
        return newHead;
    }
    /**
     * 倒数第k个结点
     */
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode prev=head;
        ListNode cur=head;
        while (k!=0) {
            cur=cur.next;
            k--;
        }
        while (cur!=null) {
            prev=prev.next;
            cur=cur.next;
        }
        return prev;
    }
    /**
     * 找出中间结点
     */
    public ListNode middleNode(ListNode head) {
        ListNode prev=head;
        ListNode cur=head;
        while (cur.next!=null&&cur.next.next!=null) {
            prev=prev.next;
            cur=cur.next.next;
        }
        return prev;
    }
    /**
     * 翻转单链表
     */
    public ListNode reverseList(ListNode head) {
        //翻转单链表
        ListNode prev=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        return prev;
    }
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    /**
     * 链表的分割
     */
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null) {
            return null;
        }
        // write code here
        //创建两个新结点
        ListNode max=null;ListNode newMax=null;ListNode min=null;ListNode newMin=null;ListNode cur=pHead;
        while (cur!=null) {
            if(cur.val<x) {
                if(min==null) {
                    min=cur;
                    newMin=min;
                }else {
                    min.next=cur;
                    min=min.next;
                }
            }else {
                if(max==null) {
                    max=cur;
                    newMax=max;
                }else {
                    max.next=cur;
                    max=max.next;
                }
            }
            cur=cur.next;
        }
        if(newMin==null) {
            return max;
        }
        min.next=newMax;
        if(max!=null)
        max.next=null;
        return newMin;
    }

    /**
     * 相交链表
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
         两个链表一起走，找出长的链表，然后长的链表先走差值，再一起走，如果相等就是相交
         */
        //长的
        ListNode maxList=headA;
        //短的
        ListNode minList=headB;
        int min=0;
        int max=0;
        while (minList!=null&&maxList!=null) {
            max++;
            min++;
            maxList=maxList.next;
            minList=minList.next;
        }
        if(maxList==null) {
            maxList=headB;
            minList=headA;
        }else {
            maxList=headA;
            minList=headB;
        }
        int count=max-min;
        while (count!=0) {
            count--;
            maxList=maxList.next;
        }
        while (minList!=maxList) {
            maxList=maxList.next;
            minList=minList.next;
        }
        return minList;
    }
}
class indexException extends RuntimeException {
    public indexException() {
    }

    public indexException(String message) {
        super(message);
    }
}